package LeetCode1;

import java.util.HashMap;
import java.util.Map;

/**
 * 复制带随机指针的链表
 * 使用map的映射存储新旧节点
 *
 * @author 是阿秋啊
 * @date 2022/03/17 15:11
 **/
public class Num138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 遍历原链表，构造新链表的节点，存储在Map中
        // Map<原链表结点，新链表结点>
        // 原1 => 新1
        Map<Node, Node> nodeMap = new HashMap<>();
        for (Node x = head; x != null; x = x.next) {
            Node node = new Node(x.val);
            nodeMap.put(x, node);
        }
        // 对新链表进行连接操作
        // 原1.next 和新1.next一一对应
        // 原1.random 和新1.random一一对应
        // 原1.next = 原3  =》新1.next = 新3(这个地址就可以根据原3来取得)
        for (Node x = head; x != null; x = x.next) {
            // 新链表的random和next和原链表一一对应
            // 对于Map来说，Key都是原链表的节点
            // 新1.next = 新3
            nodeMap.get(x).next = nodeMap.get(x.next);
            // 新1.random = 新5
            nodeMap.get(x).random = nodeMap.get(x.random);
        }
        return nodeMap.get(head);
    }
}
